package LinkedList.单循环链表;


public class SingleCircleLinkedList {
    private Node rear;
    private int size;
    static class Node{
        private int num;
        private Node next;
        public int getNum() {
            return num;
        }
        public void setNum(int num) {
            this.num = num;
        }
        public Node(int num) {
            this.num = num;
        }
    }
    public Node getHead(){
        return this.rear.next;
    }

    public Node getRear() {
        return rear;
    }

    public void setRear(Node rear) {
        this.rear = rear;
    }

    public SingleCircleLinkedList() {
        rear = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public void display(){
        System.out.println("========================");
        if (this.size==0){
            return;
        }
        Node tmp = rear.next;
        int counts = getSize();
        while((counts--)>0){
            System.out.println(tmp.getNum());
            tmp = tmp.next;
        }
        System.out.println("============OVER============");
    }
    public void addLast(int data){
        Node node = new Node(data);
        if (size==0){
            rear = node;
            rear.next = rear;
            size++;
            return;
        }
        node.next = rear.next;
        rear.next = node;
        rear = node;
        size++;
    }
    public void addNum(int num){
        if (num<1){
            System.out.println("num must >1");
            return;
        }
        for (int i = 1; i <=num; i++) {
            addLast(i);
        }
    }
    public Node getAt(int index){
        if (this.size==0){
            return null;
        }
        Node tmp = rear;
        for (int i = 1; i <=index; i++) {
            tmp = tmp.next;
        }
        return tmp;
    }
    public void removeNode(int index){
        if (size==0){
            return ;
        }
        if (index>size || index<1){
            return;
        }
        Node pre ;
        if (index==1){
            pre = rear;
        }else {
            pre = getAt(index-1);
        }
        Node rmvNode = pre.next;
        System.out.println("getOurNum:          "+rmvNode.getNum());
        pre.next = rmvNode.next;
        if (index==size){
            rear = pre;
        }
        size--;
    }
    /**
     * Joseph 问题为：设编号为1,2,···n的人围坐一圈，约定编号为k(1<=k<=n)的人开始报数，
     * 数到m的人出列，它的下一位又从1开始报数，数到m的人又开始出列，以此类推，求出圈顺序。
     */
    public void joseph(int k,int m){
        if (rear ==null || k<1 || k>size){
            System.out.println("输入有误");
            return;
        }
        Node helper = rear;
        Node first = rear.next;
        for (int i = 1; i <k; i++) {
            helper = helper.next;
            first = first.next;
        }
        while(true){
            if (helper == first){ // 最后一个节点了
                break;
            }
            for (int i = 0; i < (m-1)%size; i++) {
                helper = helper.next; // first 为删除的节点
                first = first.next;
            }
            System.out.println("小孩出圈的位置   +   "+first.getNum());
            helper.next = first.next;
            first = first.next;
            size--;
        }
        System.out.println("最后留在圈中为："+first.getNum());

    }
}
